题面

Code

#include<bits/stdc++.h>
#define INF LONG_LONG_MAX
#define ll long long
#define rgt register
#define N 100003
using namespace std;
struct node{
    int x,y;
}b[N];
int n,X[N],Y[N];
ll Sx[N],Sy[N],x,y,ans=INF,res;
inline int read() {
    rgt int s=0,p=1;
    rgt char c=getchar();
    while(!isdigit(c)) {if(c=='-') p=-1;c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*p;
}
int main()
{
    int i;
    n=read();
    for(i=1;i<=n;i++) {
        x=read(),y=read();
        X[i]=b[i].x=x+y,
        Y[i]=b[i].y=x-y;
    }
    sort(X+1,X+n+1),sort(Y+1,Y+n+1);
    for(i=1;i<=n;i++) Sx[i]=Sx[i-1]+X[i];
    for(i=1;i<=n;i++) Sy[i]=Sy[i-1]+Y[i];
    for(i=1;i<=n;i++) {
        x=lower_bound(X+1,X+n+1,b[i].x)-X;
        y=lower_bound(Y+1,Y+n+1,b[i].y)-Y;
        res=b[i].x*x-Sx[x]+Sx[n]-Sx[x]-b[i].x*(n-x);
        res+=b[i].y*y-Sy[y]+Sy[n]-Sy[y]-b[i].y*(n-y);
        ans=min(ans,res);
    }
    printf("%lld",ans>>1);
    return 0;
}

devil.